package everyday;

import org.junit.jupiter.api.Test;

public class T1043 {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        int[] leftMax = new int[k + 1];
        for (int i = 0; i < n; i++) {
            dp[i + 1] = arr[i];
            for (int j = k; j > 0; j--) {
                leftMax[j] = Math.max(arr[i], leftMax[j - 1]);
            }
            for (int j = 1; j <= k && i - j + 1 >= 0; j++) {
                dp[i + 1] = Math.max(dp[i + 1], dp[i - j + 1] + leftMax[j] * j);
            }
        }
        return dp[n];
    }

    @Test
    public void test() {
        int[] ints = {1, 10};
        System.out.println(maxSumAfterPartitioning(ints, 2));

    }
}
